package com.leetcode.simple;

import java.util.Arrays;

/**
 * 快排
 *
 * @author Administrator
 */
public class QuiteSortTest {

    public static void main(String[] args) {
        int[] ints = {9, 8, 7, 3, 2, 4, 8, 7, 82, 6, 3, 7, 6, 1, 2, 30, 19};
        quickSort(ints, 0, ints.length);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

    /*快排*/
    static void quickSort(int[] arr, int bgn, int end)  //arr must be the reference of real param
    {
        //数组arr空or仅有一个元素则退出
        if (bgn >= end - 1) {
            return;
        }
        int lindex = bgn;
        int rindex = end - 1;
        int std = arr[lindex];
        while (lindex < rindex) {
            while (lindex < rindex) {
                if (arr[rindex] < std) {
                    arr[lindex++] = arr[rindex];
                    break;
                }
                --rindex;
            }

            while (lindex < rindex) {
                if (arr[lindex] >= std) {
                    arr[rindex--] = arr[lindex];
                    break;
                }
                ++lindex;
            }
        }
        arr[lindex] = std;
        quickSort(arr, bgn, lindex);
        quickSort(arr, rindex + 1, end);
    }

}
